package LeetCode_Stack;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:括号匹配问题
 * User: 阿宾
 * Date: 2024-11-13
 * Time: 09:18
 */

/**
 * 遍历字符串中的每一个字符。
 * 如果遇到左括号（'('、'{'、'['），将其压入栈中。
 * 如果遇到右括号（')'、'}'、']'），检查栈顶元素：
 *      如果栈为空，说明没有对应的左括号，返回无效。
 *      如果栈顶元素是对应的左括号，将其弹出栈。
 *      如果栈顶元素不是对应的左括号，返回无效。
 * 遍历结束后，检查栈是否为空：
 *      如果栈为空，说明所有括号都有效闭合，返回有效。
 *      如果栈不为空，说明有未闭合的左括号，返回无效。
 */
public class Demo1 {

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }else if(c == ')' || c == ']' || c == '}'){
                //判断栈是否为空，即判断第一次入栈元素是不是直接就是右括号
                if(stack.empty()){
                    return false;
                }
                //出栈判断
                char tmp = stack.pop();
                if((c == ')' && tmp != '(') || (c == ']' && tmp != '[') || (c == '}' && tmp != '{')){
                    return false;
                }
            }
        }
        //最后判断栈是否为空，为空说明没有括号剩余，否则右括号剩余
        //([[]]
        return stack.empty();
    }
    public static void main(String[] args) {
        String s = "([[]]";
        System.out.println(isValid(s));


    }
}
